Among present databases, there is a database including data to which a label suitably to be kept in secret exceptionally is attached because each piece of data within that database belongs to an individual. For example, non-patent literature 1 discloses a technology of pseudonymization of electronic health information. Moreover, non-patent literatures 2 and 3 disclose a technology which is an encryption technology for a pseudonymization and which is called a shuffling.
The technology disclosed in non-patent literature 1 will be explained with reference to FIG. 10. An authorizer of a pseudonymization system 100 which performs pseudonymization possesses a key 101, and the pseudonymization system 100 is prepared with an encryption function 102 in a common-key encryption scheme.
When a name 104 is given from a clinical system 103 to a pseudonymization system 100, the authorizer of the pseudonymization system 100 enters the name 104 to the encryption function 102. The encryption function 102 uses the key 101 possessed by the authorizer of the pseudonymization system 100 as a key for pseudonymization. An output by the encryption function 102 is a pseudonym 105 and is passed to a research system 106.
The technology disclosed in non-patent literature 2 will be explained in detail with reference to FIG. 11. According to this technology, plural ElGamal encrypted texts 201 are input to a mixing device 200. A number of the input encrypted texts is set to be Q. Q numbers of the encrypted texts form a sequence and are added with orders.
The mixing device 200 shuffles the orders of Q numbers of the encrypted texts at random, and each encrypted text is encrypted again and is output as a new ElGamal encrypted text 202. Re-encryption means to convert the ElGamal encrypted text into a different encrypted text with a decryption result remaining same by changing a random number used in the encryption.
The sequence of the ElGamal encrypted texts 201 including Q numbers of the input encrypted texts and the sequence of the ElGamal encrypted texts 202 including the Q numbers of the encrypted texts are in a mutually corresponding relationship. That is, the latter sequence corresponds to the former sequence having the orders of respective elements being shuffled and being encrypted. This correspondence relationship is known only by a device that is capable of decrypting the ElGamal encryption or the mixing device 200 which has shuffled the orders and has performed the re-encryption.
The mixing device 200 proves that there is a one-by-one correspondence relationship between n numbers of input encrypted texts and n numbers of output encrypted texts through a zero-knowledge proof 203 while hiding the correspondence relationship. When the technology disclosed in non-patent literature 2 is used, by providing a proof through the zero-knowledge proof, it becomes possible to (1) hide the correspondence relationship between input/output, and (2) sign the presence of valid correspondence relationship between input/output.
It is known that a system called a mix-net can be configured by preparing the plural numbers of mixing devices 200 explained above. The mix-net will be explained in detail with reference to FIG. 12. It is presumed that q is a prime number, G is a cyclic group that has a difficulty in a discrete logarithm problem, and the order thereof is the prime number q. It is also presumed that g is the generator of G. The mix-net 205 that is capable of examining an ElGamal encrypted text comprises H numbers of the mixing devices, and regarding each i from 1, . . . , to H, an i-th mixing device possesses a distributed secret key x[i]εZ/qZ in an encryption scheme that satisfies a condition y[i]=gx[i]. y[i] is opened to the public and y can be expressed as a following formula.
                    y        =                              ∏                          i              =              1                        H                    ⁢                                          ⁢                      y            ⁡                          [              i              ]                                                          [                  Equation          ⁢                                          ⁢          1                ]            
Generation of an ElGamal encrypted text with a condition mεG by a public key (g, y) is to select rεZ/qZ at random and to generate (a, b)=(gr, myr).
When a sequence 204 including Q numbers of ElGamal encrypted texts is given to a first mixing device, an i-th device shuffles, from i=1 to H in order, the orders of the encrypted texts in the sequence passed from an i−1-th mixing device at random, re-encrypts individual encrypted texts independent from one another, and passes those encrypted texts to an i+1-th mixing device.
Moreover, the i-th mixing device performs zero knowledge proof that the encrypted texts in the sequence passed at the i+1-th time are merely the encrypted texts received from the i−1-th mixing device with shuffled orders of the encrypted texts and re-encrypted.
Each ElGamal text is encrypted by the public key (g, y). Re-encryption is, when, for example, an ElGamal encrypted text (a, b) is given, to covert such an encrypted text into (ags, bys) using a random sεZ/qZ. The first mixing device uses the sequence of Q numbers of the ElGamal encrypted texts input to the mix-net. An H-th mixing device passes a sequence of encrypted texts generated locally to the next operation of the mix-net.
At the end, the mix-net decrypts the sequence of the encrypted texts passed from the H-th mixing device to plain texts 206 by H numbers of mixing devices cooperating together. This decryption is performed by the H numbers of the mixing devices which cooperatively decrypt respective encrypted texts. When, for example, an ElGamal encrypted text (a, b) is given, each i-th mixing device generates a′[i]=ax[i]. The decryption result of (a, b) is b/πa′[i]. Each mixing device performs zero-knowledge proof that there is x[i] which satisfies a′[i]=ax[i] and y[i]=gx[i].
When the two zero-knowledge proofs performed by individual mixing devices, i.e., the zero-knowledge proof for shuffling of the order and re-encryption and the zero-knowledge proof for decryption are collected, those become a zero-knowledge proof 207 that the mix-net shuffled the orders of the input encrypted texts as a whole and outputs decrypted encrypted texts.
The technology disclosed in non-patent literature 3 will be explained in detail with reference to FIG. 13. This technology realizes a “mix-net that is capable of examining a hybrid encrypted text”. There are plural mixing devices according to the technology disclosed in non-patent literature 3 as well as the technology disclosed in non-patent literature 2. It is presumed that the number of the mixing device is H, numbers from 1 to H are assigned to individual mixing devices in order, and the mixing device to which a number is assigned is called an i-th mixing device.
A hybrid encrypted text 301 according to non-patent literature 3 can encrypt not an ElGamal encrypted text but a plain text having an arbitrary length unlike the encrypted text used in the technology disclosed in non-patent literature 2. Moreover, an encrypted text to be passed to the first mixing device is generated so as to be completely decrypted and become a plain text when partial decryption is performed thereon by Q times.
That is, it is presumed that q is a prime number, G is a cyclic group that has a difficulty in a discrete logarithm problem, and the order thereof is the prime number q. It is also presumed that g is the generator of G. The mix-net comprises H numbers of the mixing devices, and regarding each i from 1, . . . , to H, the i-th mixing device possesses a distributed secret key x[i]εZ/qZ for an encryption scheme that satisfies y[i]=gx[i]. y[i] is opened to the public.
Next, how to generate an encrypted text will be explained. A hybrid encrypted text with m numbers of character strings is generated as follow. It is presumed that a system parameter g of an ElGamal encrypted text and a public key (y[i]εG)i=1, . . . , H in the ElGamal encryption scheme are given. It is also presumed that senc and sdec are an encryption function and a decryption function, respectively, in the common-key encryption scheme, and K is a space of the key. It is also presumed that an m encryption relating to χεK is senc (χ, m) and the decryption thereof is sdec (χ, senc (χ, n))=m. It is also presumed that ψ can be calculated through an one-by-one function from K to G, and can be calculated in a reverse manner.
First, χ[i]εK and r[i]εZ/qZ which are selected at random regarding each i=1, . . . , H are prepared. Next, m[i−1]=(gr[i], ψ(χ[i])y[i]r[i], senc (χ[i], m[i])) is generated with m[H]=m from i=H to 1 in a descending order, and m[0] is set as an encrypted text.
Next, a mix-net processing of a hybrid encryption will be explained in detail. A mix-net 300 that is capable of examining a hybrid encrypted text is a system including H numbers of the mixing devices that cooperatively work to execute a process as follow. When a sequence 301 including Q numbers of hybrid encrypted texts is given to the first mixing device, from i=1 to H in an order, each i-th mixing device shuffles the orders of the encrypted texts in the sequence passed from an i−1-th mixing device at random, partially decrypts individual encrypted texts to generate a set of Q numbers of the encrypted texts, and passes such a set to an i+1-th mixing device.
Moreover, the i-th mixing device performs zero-knowledge proof that the encrypted texts in the sequence passed at the i+1-th time are merely encrypted texts which are received from the i−1-th mixing device with shuffled order and partially decrypted. Q numbers of the encrypted texts are directly input to the first mixing device as well as the technology disclosed in non-patent literature 2. An H-th mixing device outputs a sequence of decrypted plain texts 302. The whole zero-knowledge proof is a validity proof 303 by the hybrid mix-net.
The hybrid encrypted text is encrypted by a public key (g, (y[i])i=1, . . . , H). The partial decryption is, when, for example, m[i−1]=(a[i], b[i], c[i])=(gr[i], ψ(χ[i])y[i]r[i], senc (χ[i], m[i])) is given to the i-th mixing device, to generate an output which is ψ[i]=b[i]/a[i]x[i], m[i]=sdec (ψ[i], c[i]).